package com.leetcode;

import java.util.*;

/**
 * 127. 单词接龙
 * TODO: 待研究图的算法
 * 广度优先搜索 + 优化建图
 * 构造图并进行图的广度优先遍历
 * 我们可以把每个单词都抽象为一个点，如果两个单词可以只改变一个字母进行转换，那么说明他们之间有一条双向边
 */
public class Solution127 {
    // 单词与节点id的对应关系
    Map<String, Integer> wordId = new HashMap<>();
    // 图的邻接表数据
    List<List<Integer>> edge = new ArrayList<>();
    // 节点数
    int nodeNum = 0;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        for (String word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        // 如果结束单词不在变化列表里则没法转换到
        if (!wordId.containsKey(endWord)) {
            return 0;
        }
        // 开始节点遍历到对应下标的节点的路径长度，默认填充为最大长度
        int[] dis = new int[nodeNum];
        Arrays.fill(dis, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord);
        int endId = wordId.get(endWord);
        // 当前节点到自己的距离是0
        dis[beginId] = 0;

        // 广度优先遍历使用队列
        Queue<Integer> que = new LinkedList<>();
        // 先将开始节点入队
        que.offer(beginId);
        while (!que.isEmpty()) {
            int x = que.poll();
            // 当搜索到终点时，我们就找到了最短路径的长度。
            // 注意因为添加了虚拟节点，所以我们得到的距离为实际最短路径长度的两倍。
            // 同时我们并未计算起点对答案的贡献，所以我们应当返回距离的一半再加一的结果。
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            // 遍历所有与该节点相邻的节点。如果之前没有访问过则距离+1入队
            for (int it : edge.get(x)) {
                if (dis[it] == Integer.MAX_VALUE) {
                    dis[it] = dis[x] + 1;
                    que.offer(it);
                }
            }
        }
        // 如果与endId节点不连通则返回0
        return 0;
    }

    /**
     * 构建节点图的邻接表
     * 通过添加虚拟节点
     *
     * @param word
     */
    private void addEdge(String word) {
        // 初次初始化
        addWord(word);
        int id1 = wordId.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        // 通过添加虚拟节点来转换为相差一个字母的其他单词
        for (int i = 0; i < length; ++i) {
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            // 添加虚拟节点
            addWord(newWord);
            int id2 = wordId.get(newWord);
            // 因为是无向图，所以添加两条边
            edge.get(id1).add(id2);
            edge.get(id2).add(id1);
            // 还原原字符
            array[i] = tmp;
        }
    }

    /**
     * 将单词节点及虚拟单词节点放入hashmap中方便查看是否已经建立过边
     *
     * @param word
     */
    private void addWord(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word, nodeNum++);
            edge.add(new ArrayList<>());
        }
    }

    public static void main(String[] args) {
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = new ArrayList<String>() {
            {
                add("hot");
                add("dot");
                add("dog");
                add("lot");
                add("log");
                add("cog");
            }
        };
        int res = new Solution127().ladderLength(beginWord, endWord, wordList);
        System.out.println(res);
    }

}
